データモデルとクエリ言語 from DDIA
Chapter 2. Data Models and Query Languages
システムにおけるデータモデルが重要なのは、プログラミングに影響を及ぼすだけではなく、我々自身の問題の捉え方を制約しうるからだ 「あるデータモデルは下のレイヤでどう表現されるか?」はシステム設計の主要な問題である
ソフトウェアエンジニアリングが抽象化の層を用いて問題を分割してきたことから、問題はその層間の対応に現れる
例えば4つの層に分けられる
1. アプリケーション開発者は現実世界におけるオブジェクトやリレーションをデータ構造で表現する
ユーザアカウント、グループ、アイテム、アクション、フロー、センサーなど
そういったものはAPIで操作され、下のレイヤへ送られる
2. あなたはそれらを汎用的なデータモデル、例えばJSONやXML、RDBやグラフDBで表現する
特に本章では1を2でどう表現するかを見ていく
3. ミドルウェア開発者はそれらデータモデルをメモリやストレージ、ネットワーク上のバイトモデルで表現する
第三章ではここを見ていく
4. ハードウェア開発者はバイトモデルを電磁気的に表現する
実際にはより細分化されうる
60-70年代、メインフレームコンピュータを用いてビジネスに必要なデータを処理する取り組みがあった
トランザクション処理やバッチ処理など
Relational Modelはデータベース内の実装を隠し、共通の理論的なインターフェースを与えるのが目的だった
その後2000年代くらいまでDocument Modelとか色々出てるけど流行らなかった
2010年代からNoSQLというバズワードで再流行する オープンソースのミートアップにて使われたtwitterのハッシュタグが由来らしい
Not Only SQLらしい
je6bmq.icon OOPが普及した世の中で、ORマッパーに起きがちなDBとアプリケーションコード間の効率的とは思えない変換レイヤが必要となっていることについて、「インピーダンス不整合」と表現しているのは言いえて妙だと思う
プロフィール画面のような複数の属性を表す場合(1ユーザidに複数の属性がぶら下がる1:N関係)
RDBだと複数のテーブルが散在し、取得時に相互の関係を記述して構成する
JSONで表現されるドキュメントDBはローカリティが高いのでRDBに比べ幾つかうれしさがある
正規化されたRDBは木構造が暗黙的に表現され、ユーザが組み立てなければならない
RDBの正規化、非正規化による性質は第三章で
JSONは明示的に木構造が表現される
JSONにはデータフォーマットとしての問題点があるがそれは4章で
逆にN:1関係の場合(複数のユーザが一つの企業や国などの属性をもつ関係)
RDBはその属性でJOINすればいいので簡単
IDでテーブルを分離する考えは表記が統一される他にも、変更しやすさ、ローカライゼーション対応、検索性の向上、補完機能の選択肢など、色々利点がある
JSONのドキュメントDBではJOINサポートが弱いので、1:N関係を作った状態でN:1を作るのは楽ではない
動的さが失われるが、JOINのためのプリミティブを用意しているドキュメントDBもある
テキスト埋め込みなドキュメントDBを使う場合、後から仕様が増築されてN:Nな関係になると大変
端的に言えば複雑なリンク構造が必要になってきた場合に文字列埋め込みだと辛いよって話
ドキュメントDBはDBの歴史を繰り返しているのか?
歴史の話なのでざっくりと
アポロ計画の在庫管理などに向けて開発されたIBMのIMS(Information Management System)はHierarchical modelというデータベースだった これがJSONを用いたドキュメントDBに幾つかの側面で似ている
1:Nは得意だがN:Nが苦手でJOINができない
結果的にはデータを複製することになり、人手で参照を解決する必要も生じた
Hierarchical modelのカウンターがRelational modelとNetwork modelだった
Network modelは始め隆盛したが最終的に消え去った
Network modelはそれを作ったコミッティーからCODASYLモデルとも呼ばれる Hierarchicalをベースに、キーの代わりにポインタを持ち複数の親を持つことを許可した
当時のパフォーマンス的には良かったが、望みのデータを探したり計算するのが大変だった
avashe.icon 密結合のネットワーク構造と考えると、次第に複雑化し変更できなくなる様が想像できる
ただしDocument modelはDocument referenceとよばれるSQLでいうところのforeign keyを持っているため、CODASYLの二の舞を免れている
他にもRethink DBのRelational like joinやMongo DBの外部参照解決機能など
前述した構造的な差は変わらないが、より関係が複雑なもののためにGraph DBが選択肢として入った
暗黙的にschemeは定まっており、読み方を間違えれば失敗するのだから
プログラミングにおける動的型付けのようなものだ
RDBサイドにもJSONドキュメントなどを要素として持てるようになった
Schemaの有無が次第に曖昧になっていくのはプログラミング言語の漸進的型付けの流行に似ている
静的型付けvs動的型付けは結論が出ない話なので避けるが、それらの議論で言われるように、Schemaの有無というのはDBのフォーマットを変更する際の特性が異なってくるのが重要だ
schema-on-readであれば実行時に解釈するか、jsonを書き換えるスクリプトを書いて回すなどする
schema-on-writeであればschemaを変更するシステムの機能を使う
大体データレイアウトが固定されてるのでテーブルを変更するALTER TABLEは高速だったりする
MySQLという有名な例外を除いて...
クエリに対するデータ局所性
素朴に考えるとRDBのように参照によってテーブルの物理位置が分離しているものに対し、文字列の集まりであるDoc DBではStorage localityがある
まぁそもそも最近のRDBもJSONを持てる
現実では勿論各DBが必要な局所性を取り込める工夫を凝らしている
Google SpannerやOracleによるmulti-table index cluster tabesやCassandra, HBaseで知られるcolumn-familyなど
Chapter 3でこの話はちゃんとやる
宣言的な言語は得たい結果の記述と実装が切り離されている
並列処理を実装として宛てることもできるし、Query Optimizerにも投げられる
手続き的な記述は暗黙的に逐次的処理、つまり時系列的な依存関係を与えている
その時点で実装を記述してしまっている
MongoDBは2.2からaggregation pipelineという比較的宣言的な記法を導入したよ
N:Nどころか保存するデータがheterogeneousな場合グラフを利用する手がある
またはデータ間の関係が非常に複雑な場合
頂点のtypeであればユーザ、国、町などなど
辺のtypeであれば「AはBをフォロー」、「AはBに属す」、「AはBに住んでいる」などなど
グラフ的データモデルの構造化手法には大別して二種類ある
property graph model
Neo4j, Titan, InfiniteGraphなど
triple-store mode
Datomic, AllegroGraphなど
クエリ言語も何種類かある
Cypher
SPARQL
Datalog
点は以下からなる
ユニークな識別子
この点から出る辺の集合
この点に入る辺の集合
点を表すプロパティ(key-valueドキュメント)
辺は以下からなる
ユニークな識別子
この辺が出る点(the tail vertex)
この辺が入る点(the head vertex)
二つの点を結ぶ関係(ラベル)
辺を表すプロパティ(key-valueドキュメント)
このモデルにおける重要な性質
あらゆる点は何らかの点とつながっている辺をもつこと
検索のためにtail vertexとhead vertexのインデックスを構築しておく必要がある
avashe.icon必須ではないだろうけど、TAOの例を表すなら点にもtypeを表すラベルが欲しい
点と辺をこのように表せばそれぞれschemaを定義できる
あとtypeのテーブルもあればいい
GraphというEvolvabilityの高い構造もDBで保存できる
Cypher
Neo4jの人たちがproperty graphのために作った宣言的クエリ言語
名前は暗号には特に関係なく、映画マトリックス由来らしい
特徴的なグラフの記法で新しい辺を挿入したり、グラフの形でパターンマッチして辺や点のプロパティを取り出す
(node-name-a) -[:label]-> (node-name-b) 的な
これをSQLで再現するとどうなるかという話が展開されてる
Cypherで4行で書けるものが24行かかる
よくある適切なモデルを選ぼうという話なので省略
triple-storeモデルは実はproperty modelと同じアイデアを異なる言葉で記述しただけ
それでもtriple-storeモデルで作られたツールは多岐にわたるので知っておくと有用
triple-storeは全ての情報を(subject, predicate, object)の三要素で保存するモデル
subjectはグラフの点
objectは2つの要素のいずれか(predicateも場合によってくる)
プリミティブな値、文字列や数
この場合点のプロパティの定義になる
subjectが点、predicateがkeyでobjectがvalue
subjectと異なるグラフの点
subjectはtail vertex, predicateは辺、objectはhead vertex
triple-storeモデルはsemantic webという取り組みと関係がある
Webはコンテンツを公開し、人間が読める世界になったが、機械にはそれを理解できない
テキストや画像のメタ情報をグラフ構造で記述する枠組みを用意し、Web上のリソースの意味を一貫して機械可読な世界にしたかった
TurtleはRDFの一種で、記述のtripleにURIが使える(Web要素)
かつて2000年代に流行ったが消えた、その後はwikipediaのデータ形式や情報学と親和する領域で影響が残っている
avashe.icon機械学習とかでwikipediaのDBを漁ったことがある人なら見かけたことあるはず
Graph DBはNetwork model(CODASYL)の二の舞にならない
CODASYLではパスを直接記述しないと目的のノードを参照できなかった
GraphではIDで直接参照可能
CODASYLでは命令型のクエリだけなのでクエリのメンテナンス性が低かった
Graphでも直接参照を選べるが、高レベルのクエリ言語は基本的に宣言的記述である
CODASYLでは子のレコード群が順序付き集合なので挿入などで順序を気にする必要があった
Graphではその必要がない
avashe.icon(これは実装の都合な気もするが)
1980sにアカデミアで作られたクエリ言語の基礎
Datalogの記法はPrologのサブセット
論理プログラミング言語としての性質が協力
基本的な値の記述はTriple-store modelよろしく主語述語目的語の論理式
この論理式を一部変項にすることで、DBから該当する変項を検索できる
勿論関数プログラミングの関数よろしく論理式の組み合わせからなるRuleを記述できる
Ruleが再利用性&合成性のある値の記述であると同時に、宣言的な検索でもあるのが非常に強力
つまり「Xな属性を持つ値A」というRuleを定義すれば、Aを具体化して挿入することもできるし、変項Aとして検索することもできるこの一挙両得さ
avashe.icon 個人的にはセンスの良さを感じる
SQLに対してActiveRecordパターンなどが良いとされるのは、勿論関数プログラミングとオブジェクト指向プログラミングのずれもあるが、SQLが変数や関数を記述できず、再利用性と合成性の面で劣るのが問題
この辺をうまく調停しようとする取り組みにはLINQがある
再利用性と合成性に優れるクエリ言語があれば、全て解決というわけだ
つか普通にこの辺は関数プログラミングの方が親和性があるし、ClojureでDatalog方言を実装したDatomicは本当に良いところに目を付けたと思う